{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 线性数据结构\n",
    "\n",
    "## 列表\n",
    "\n",
    "在对基本数据结构的讨论中，我们使用 Python 列表来实现所呈现的抽象数据类型。列表是一个强大但简单的收集机制，为程序员提供了各种各样的操作。然而，不是所有的编程语言都包括列表集合。在这些情况下，列表的概念必须由程序员实现。\n",
    "\n",
    "列表是项的集合，其中每个项保持相对于其他项的相对位置。更具体地，我们将这种类型的列表称为无序列表。我们可以将列表视为具有第一项，第二项，第三项等等。我们还可以引用列表的开头（第一个项）或列表的结尾（最后一个项）。为了简单起见，我们假设列表不能包含重复项。\n",
    "\n",
    "例如，整数 `54,26,93,17,77` 和 `31` 的集合可以表示考试分数的简单无序列表。请注意，我们将它们用逗号分隔，这是列表结构的常用方式。当然，Python 会显示这个列表为 `[54,26,93,17,77,31] `。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 无序列表\n",
    "\n",
    "### 抽象数据类型\n",
    "如上所述，无序列表的结构是项的集合，其中每个项保持相对于其他项的相对位置。下面给出了一些可能的无序列表操作。\n",
    "\n",
    "* List() 创建一个新的空列表。它不需要参数，并返回一个空列表。\n",
    "* add(item) 向列表中添加一个新项。它需要 item 作为参数，并不返回任何内容。假定该 item 不在列表中。\n",
    "* remove(item) 从列表中删除该项。它需要 item 作为参数并修改列表。假设项存在于列表中。\n",
    "* search(item) 搜索列表中的项目。它需要 item 作为参数，并返回一个布尔值。\n",
    "* isEmpty() 检查列表是否为空。它不需要参数，并返回布尔值。\n",
    "* size（）返回列表中的项数。它不需要参数，并返回一个整数。\n",
    "* append(item) 将一个新项添加到列表的末尾，使其成为集合中的最后一项。它需要 item 作为参数，并不返回任何内容。假定该项不在列表中。\n",
    "* index(item) 返回项在列表中的位置。它需要 item 作为参数并返回索引。假定该项在列表中。\n",
    "* insert(pos，item) 在位置 pos 处向列表中添加一个新项。它需要 item 作为参数并不返回任何内容。假设该项不在列表中，并且有足够的现有项使其有 pos 的位置。\n",
    "* pop() 删除并返回列表中的最后一个项。假设该列表至少有一个项。\n",
    "* pop(pos) 删除并返回位置 pos 处的项。它需要 pos 作为参数并返回项。假定该项在列表中。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 实现无序列表\n",
    "\n",
    "为了实现无序列表，我们将构造通常所知的**链表**。回想一下，我们需要确保我们可以保持项的相对定位。然而，没有要求我们维持在连续存储器中的定位。例如，考虑下图中所示的项的集合。看来这些值已被随机放置。\n",
    "![3.21.实现无序列表：链表.figure1](figures/3.21.%E5%AE%9E%E7%8E%B0%E6%97%A0%E5%BA%8F%E5%88%97%E8%A1%A8%EF%BC%9A%E9%93%BE%E8%A1%A8.figure1.png)\n",
    "\n",
    "如果我们可以在每个项中保持一些明确的信息，即下一个项的位置（参见下图），则每个项的相对位置可以通过简单地从一个项到下一个项的链接来表示。\n",
    "\n",
    "![3.21.实现无序列表：链表.figure2](figures/3.21.%E5%AE%9E%E7%8E%B0%E6%97%A0%E5%BA%8F%E5%88%97%E8%A1%A8%EF%BC%9A%E9%93%BE%E8%A1%A8.figure2.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "要注意，必须明确地指定链表的第一项的位置。一旦我们知道第一个项在哪里，第一个项目可以告诉我们第二个是什么，等等。**外部引用通常被称为链表的头**。类似地，最后一个项需要知道没有下一个项。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### Node 类\n",
    "\n",
    "链表实现的基本构造块是节点。每个节点对象必须至少保存两个信息。首先，节点必须包含列表项本身。我们将这个称为节点的数据字段。此外，每个节点必须保存对下一个节点的引用。 下面代码展示了 链表的节点的Python 实现。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, initdata):\n",
    "        self.data = initdata\n",
    "        self.next = None\n",
    "\n",
    "    def getData(self):\n",
    "        return self.data\n",
    "\n",
    "    def getNext(self):\n",
    "        return self.next\n",
    "\n",
    "    def setData(self, newdata):\n",
    "        self.data = newdata\n",
    "\n",
    "    def setNext(self, newnext):\n",
    "        self.next = newnext"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "要构造一个节点，需要提供该节点的初始数据值。下面的赋值语句将产生一个包含值 93 的节点对象（见下图）。\n",
    "![3.21.实现无序列表：链表.figure3](figures/3.21.%E5%AE%9E%E7%8E%B0%E6%97%A0%E5%BA%8F%E5%88%97%E8%A1%A8%EF%BC%9A%E9%93%BE%E8%A1%A8.figure3.png)\n",
    "\n",
    "\n",
    "应该注意，我们通常会如下图所示表示一个节点对象。Node 类还包括访问，修改数据和访问下一个引用的常用方法。\n",
    "![3.21.实现无序列表：链表.figure4](figures/3.21.%E5%AE%9E%E7%8E%B0%E6%97%A0%E5%BA%8F%E5%88%97%E8%A1%A8%EF%BC%9A%E9%93%BE%E8%A1%A8.figure4.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们可以通过如下的代码创建一个 Node 对象。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<__main__.Node object at 0x000001D61E000AC0>\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "93"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "temp = Node(93)\n",
    "print(temp)\n",
    "temp.getData()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python 引用值 None 将在 Node 类和链表本身发挥重要作用。引用 None 代表没有下一个节点。请注意在构造函数中，最初创建的节点 next 被设置为 None。有时这被称为 **接地节点**，因此我们使用标准接地符号表示对 None 的引用。将 None 显式的分配给初始下一个引用值是个好主意。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class UnorderedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self.head == None\n",
    "\n",
    "    def add(self, newnode):\n",
    "        self.head = newnode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "templist = UnorderedList()\n",
    "print(templist.isEmpty())\n",
    "templist.add(Node(93))\n",
    "print(templist.isEmpty())"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "0ba00dd77806596ecbc07d55b4ddf41b2ae8cecbf91d9534027e74a33368b668"
  },
  "kernelspec": {
   "display_name": "Python 3.8.3 64-bit ('base': conda)",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
